package computationalgeometry;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

//凸包，也就是包含所有点的凸多边形
public class ConvexHull {
	
//	http://blog.csdn.net/bone_ace/article/details/46239187
	
	// 蛮力法算法思路：对于一个n个点集合中的两点pi和pj，当且仅当该集合中的其它点都位于穿过pi和pj所构成直线的同一边.
	// 对每一对点都做一遍检查后，满足条件的线段构成了该凸包的边界。

	//ax + by - c == 0用于表述一条直线
	//a = y2 - y1, b = x1 - x2. c = x1y2 - y1x2
	// 两个点构成一条直线，直线把平面分为两个半平面：其中一个平面上所有的点都满足ax + by - c > 0
	// 而另一个半平面中的点满足ax + by - c < 0
	
	public static void main(String[] args) {
		List<Point> set = new ArrayList<>();
//		set.add(new Point(9.0F, -16.0F));
//		set.add(new Point(9.5F, 13.0F));
//		set.add(new Point(-36.0F, -10.0F));
//		set.add(new Point(-8.5F, -5.5F));
//		set.add(new Point(27.0F, 7.0F));
//		set.add(new Point(20.5F, 19.0F));
//		set.add(new Point(-22.5F, 19.0F));
//		set.add(new Point(-14.0F, 8.0F));
		set.add(new Point(0, 0));
		set.add(new Point(2, 3));
		set.add(new Point(5, 1));
		set.add(new Point(5, 9));
		set.add(new Point(1, 5));
		set.add(new Point(-2, 4));
		set.add(new Point(-1, 3));
		set.add(new Point(-5, 1));
		
//		List<Point> convexSet = convexHull(set); 
		ConvexHull object = new ConvexHull();
		object.init(set);
		List<Point> convexSet = object.graham(set); 
		for (int i = 0; i < convexSet.size(); i++) {
			System.out.print("(" + convexSet.get(i).x + ", " + convexSet.get(i).y + ")  ");
			if (i % 2 == 1) {
				System.out.println();
			}
		}
	}
	
	//使用穷举法得到凸包
	public static List<Point> convexHull(List<Point> pointsSet){
		List<Point> res = new ArrayList<>();
		int size = pointsSet.size();
		if(size <= 2){
			return res;
		}
		for(int i = 0; i < size - 1; i++){
			for(int j = i + 1; j < size; j++){
				float a = pointsSet.get(j).y - pointsSet.get(i).y;
				float b = pointsSet.get(i).x - pointsSet.get(j).x;
				float c = pointsSet.get(i).x * pointsSet.get(j).y - 
						pointsSet.get(i).y * pointsSet.get(j).x;
				List<Point> signEqualVec = new ArrayList<>();
				signEqualVec.add(pointsSet.get(i));
				signEqualVec.add(pointsSet.get(j));
				//位于同一边的个数
				int posCount = 0, negCount = 0;
				for (int k = 0; k < pointsSet.size(); k++) {
					if (k == i || k == j)
						continue;
					//计算位于哪一边
					float sign = a * pointsSet.get(k).x + b
							* pointsSet.get(k).y - c;
					if (sign == 0){
						//在该直线上
						signEqualVec.add(pointsSet.get(k));
					} else if (sign > 0){
						posCount++;
					} else if (sign < 0){
						negCount++;
					}
				}
				//如果两边都有，那么不是凸包的边界
				if (posCount > 0 && negCount > 0) {
					continue;
				}
				int curSize = signEqualVec.size();
				for (int m = 0; m < curSize; m++) {
					res.add(signEqualVec.get(m));
				}
			}
		}
		return res;
	}
	
	//分治法  点到直线的距离公式 ： d = |Ax0 + By0 + C| / sqrt(A ^ 2 + B ^ 2)
	//(x0,y0)为点的坐标，Ax + By + C = 0为直线的方程
	
	//时间复杂度：O(nlogn)。 
//	思路：应用分治法思想，把一个大问题分成几个结构相同的子问题，把子问题再分成几个更小的子问题……。然后我们就能用递归的方法，分别求这些子问题的解。最后把每个子问题的解“组装”成原来大问题的解。 
//	步骤：
//
//	1. 把所有的点都放在二维坐标系里面。那么横坐标最小和最大的两个点 P1 和 Pn 一定是凸包上的点
	// 直线 P1Pn 把点集分成了两部分，即 X 轴上面和下面两部分，分别叫做上包和下包。
//	2. 对上包：求距离直线 P1Pn 最远的点，即下图中的点 Pmax 。
//	3. 作直线 P1Pmax 、PnPmax，把直线 P1Pmax 左侧的点当成是上包，把直线 PnPmax 右侧的点也当成是上包。
//	4. 重复步骤 2、3。
//	5. 对下包也作类似操作。
	
//	在步骤一，如果横坐标最小的点不止一个，那么这几个点都是凸包上的点，此时上包和下包的划分就有点不同了，需要注意。
	
	
	
	
	//Gerham扫描

	private static final double PRECISION = 0.00000001;
	private Point pointStart;

	//求叉积
	float cross(Point point, Point point1, Point point2){
		float x1 = point1.x - point.x;
		float y1 = point1.y - point.y;
		float x2 = point2.x - point.x;
		float y2 = point2.y - point.y;
		
		//向量的叉积为x1y2 - x2y1
		return x1 * y2 - x2 * y1;
	}
	
	// 求两点间的距离
	double dis(Point a, Point b){
	    return  Math.sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
	}
	
	// 排序，求凸包
	public void init(List<Point> pointsSet){
	    find(pointsSet);
	    Collections.sort(pointsSet, new Comparator<Point>() {
	    	@Override
	    	public int compare(Point a, Point b) {
	    		//极坐标排序
	    		double x = cross(pointStart, a, b);
	    	    if(x > PRECISION) return -1;
	    	    else if(x < -PRECISION) return 1;
	    	    //如果共线，那么将取距离较远的
	    	    a.length = dis(pointStart, a);
	    	    b.length = dis(pointStart, b);
	    	    double diff = a.length - b.length;
				if (diff > PRECISION){
					return 1;
				} else if (diff < -PRECISION){
					return -1;
				}else{
					return 0;
				}
	    	}
		});
	    System.out.println("start: " + pointStart);
	    System.out.println(pointsSet);
	    // graham(pointsSet);
	}
	
	//查找起始点，最下面的那个，如果多个y值最小，取x值最小的
	public void find(List<Point> pointsSet){
	    int temp = 0;
	    Point a = pointsSet.get(0);
	    int n = pointsSet.size();
		for (int i = 0; i < n; i++) {
			if (pointsSet.get(i).y < a.y || pointsSet.get(i).y == a.y && pointsSet.get(i).x < a.x) {
				a = pointsSet.get(i);
				temp = i;
			}
		}
		//交换
		pointsSet.set(temp, pointsSet.get(0));
	    pointsSet.set(0, a);
	    // 保存起始点
	    pointStart = a;
	}
	
	//Graham扫描法
	
	
//	http://www.cnblogs.com/Booble/archive/2011/03/10/1980089.html
//	这篇博客写的很好，指出了极坐标排序时的一个矛盾
	
//	1. 把所有点放在二维坐标系中，则纵坐标最小的点一定是凸包上的点，如图中的P0。
//	2. 把所有点的坐标平移一下，使 P0 作为原点，如上图。(这一步没啥必要，因为计算向量和距离)
//	3. 计算各个点相对于 P0 的幅角 α ，按从小到大的顺序对各个点排序。当 α 相同时，距离 P0 比较近的排在前面。
//	例如上图得到的结果为 P1，P2，P3，P4，P5，P6，P7，P8。我们由几何知识可以知道。
//	结果中第一个点 P1 和最后一个点 P8 一定是凸包上的点。 
//	（以上是准备步骤，以下开始求凸包） 
//	4. 以上，我们已经知道了凸包上的第一个点 P0 和第二个点 P1，我们把它们放在栈里面。
//	现在从步骤3求得的那个结果里，把 P1 后面的那个点拿出来做当前点，即 P2 。接下来开始找第三个点：
//	5. 连接P0和栈顶的那个点，得到直线 L 。看当前点是在直线 L 的右边还是左边。如果在直线的右边就执行步骤5；
//	如果在直线上，或者在直线的左边就执行步骤6。
//	5. 如果在右边，则栈顶的那个元素不是凸包上的点，把栈顶元素出栈。执行步骤4。
//	6. 当前点是凸包上的点，把它压入栈，执行步骤7。
//	7. 检查当前的点 P2 是不是步骤3那个结果的最后一个元素。是最后一个元素的话就结束。
//	 	如果不是的话就把 P2 后面那个点做当前点，返回步骤4。
	public List<Point> graham(List<Point> pointsSet){
		int top = 2;
		List<Point> res = new ArrayList<>();
		res.add(pointsSet.get(0));
		res.add(pointsSet.get(1));
		res.add(pointsSet.get(2));
		
		int n = pointsSet.size();
		for (int i = 3; i < n; i++) {
			while (top > 1 && cross(res.get(top - 1), res.get(top), pointsSet.get(i)) <= PRECISION ){
				top--;
			}
			int size = res.size();
			if(++top >= size){
				res.add(pointsSet.get(i));
			}else{
				res.set(top, pointsSet.get(i));
			}
		}
		return res;
	}
}
